# date:20210201
from typing import List
import collections


# 此解法超时
class Solution:
    def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:
        avg = (sum(A) - sum(B))/2
        for i in A:
            for j in B:
                if i == j + avg:
                    return [i, j]


# 用时：5.11% 内存：39.11%
class Solution:
    def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:
        avg = (sum(A) - sum(B))/2
        for i in A:
            if i - avg in B:
                return [i, i-avg]


# 用时：71.61% 内存：33.24%
# 使用hash表
class Solution:
    def fairCandySwap(self, A: List[int], B: List[int]) -> List[int]:
        avg = (sum(A) - sum(B))/2
        B = collections.Counter(B)
        for i in A:
            if i - avg in B:
                return [i, i-avg]


A = [1, 2]
B = [2, 3]
model = Solution()
print(model.fairCandySwap(A, B))

A = [1, 2, 5]
B = [2, 4]
print(model.fairCandySwap(A, B))

B = [1, 2, 5]
A = [2, 4]
print(model.fairCandySwap(A, B))

